import java.util.LinkedList;
import java.util.Queue;

// 对图进行广度优先搜索
public class BreadthFirstTraversal {
    // 索引代表顶点，值代表当前顶点是否已经被搜索过
    private boolean[] marked;
    // 记录有多少个顶点与 顶点 vertex 相通
    private int count;
    // 用来存储带搜索的邻接表的顶点
    private Queue<Integer> waitSearchQueue;
    // 指定顶点
    private int vertex;

    public BreadthFirstTraversal(Graph graph, int vertex) {
        this.marked = new boolean[graph.getApexNum()];
        this.count = 0;
        this.vertex = vertex;
        this.waitSearchQueue = new LinkedList<>();
        bfs(graph, vertex);
    }

    /**
     * 使用广度优先搜索找出 graph 图 中 v顶点的所有 相邻顶点
     * @param graph
     * @param v
     */
    private void bfs(Graph graph, int v) {
        this.waitSearchQueue.offer(v);
        marked[v] = true;
        count++;
        while (!waitSearchQueue.isEmpty()) {
            int tmp = waitSearchQueue.peek();
            for (Integer integer : graph.adj(tmp)) {
                if (!marked[integer]) {
                    // 标记已经访问
                    marked[integer] = true;
                    waitSearchQueue.offer(integer);
                    System.out.println(tmp+" ——> "+integer);
                }
            }
            this.count++;
            waitSearchQueue.poll();

        }
    }

    /**
     * 判断 w 点和 顶点 vertex 是否相通
     * @param w
     * @return
     */
    public boolean marked(int w) {
        if (w >= this.marked.length) {
            // 越界
            return false;
        }
        return this.marked[w];
    }

    /**
     * 获取与 顶点 vertex 相连通的所有顶点的总数
     * @return
     */
    public int getCount() {
        return count;
    }

}
